void World::detect()
{
	double ballx = ball.loc[0];
	double bally = ball.loc[1];
	double ballz = ball.loc[2];

	double vballx = ball.vel[0];
	double vbally = ball.vel[1];
	double vballz = ball.vel[2];
	double ballspeed = ball.vel.length();

	double radius = ball.radius + epsilon;
	Vector ballPos = ball.loc;
	Vector ballNextPos = ball.getNextLoc(timeLeft);

#if DEBUG
cerr << "Ball's next position is (" << ballNextPos[0] << ", " << ballNextPos[1] << ", " << ballNextPos[2] << ")" << endl;
#endif

	bool collided = false;
	Vector normal = Vector();
	double timeElapsed = timeLeft;

	// Go through all the triangles and check for collisions.
	for (int i = 0; i < nTri; i++)
	{
#if DEBUG
		cerr << "Performing collision detection on triangle " << i << endl;
#endif

		double triangleCollisionTime = TIME_PER_STEP;
		bool collidedThisTime = false;
		Vector normalToAdd = Vector();

		// This is for edge detection.
		Vector v1 = triangles[i].verts[0];
		Vector v2 = triangles[i].verts[1];
		Vector v3 = triangles[i].verts[2];

		/*
		 * Vertex detection.
		 */

		// Find alpha.
		double v1testalpha = linePointMinimumDistance(ballPos, ballNextPos, v1);
		double v2testalpha = linePointMinimumDistance(ballPos, ballNextPos, v2);
		double v3testalpha = linePointMinimumDistance(ballPos, ballNextPos, v3);
		
		// Find the closest point, knowing that the closest point 
		// q = start + (end - start) * alpha.
		Vector v1testpoint = ballPos + (ballNextPos - ballPos) * v1testalpha;
		Vector v2testpoint = ballPos + (ballNextPos - ballPos) * v2testalpha;
		Vector v3testpoint = ballPos + (ballNextPos - ballPos) * v3testalpha;

		// Find the distance between the closest pointon the line to the vertex.
		double v1test = (v1testpoint - v1).length();
		double v2test = (v2testpoint - v2).length();
		double v3test = (v3testpoint - v3).length();

		/*
		 * Edge detection.
		 */

		// Find alphas and betas.
		double alpha1to2, alpha2to3, alpha3to1;
		double beta1to2, beta2to3, beta3to1;
		lineLineMinimumDistance(ballPos, ballNextPos, v1, v2, alpha1to2, beta1to2);
		lineLineMinimumDistance(ballPos, ballNextPos, v2, v3, alpha2to3, beta2to3);
		lineLineMinimumDistance(ballPos, ballNextPos, v3, v1, alpha3to1, beta3to1);

		// Use the alphas and betas to find the closest points on each linem and find the
		// distance between these points. We know that
		//		p1 = start1 + alpha * (end1-start1)
		//		p2 = start2 + beta * (end2-start2)
		// where p1 is the closest point on line 1, which is the line of motion for the
		// ball and p2 is the closest point on line 2, which is the edge.
		Vector e1to2line1point = ballPos + (ballNextPos - ballPos) * alpha1to2;
		Vector e1to2line2point = v1 + (v2 - v1) * beta1to2;
		double e1to2test = (e1to2line2point - e1to2line1point).length();

		Vector e2to3line1point = ballPos + (ballNextPos - ballPos) * alpha2to3;
		Vector e2to3line2point = v2 + (v3 - v2) * beta2to3;
		double e2to3test = (e2to3line2point - e2to3line1point).length();

		Vector e3to1line1point = ballPos + (ballNextPos - ballPos) * alpha3to1;
		Vector e3to1line2point = v3 + (v1 - v3) * beta3to1;
		double e3to1test = (e3to1line2point - e3to1line1point).length();

		/*
		 * Standardize the ball's position and velocity.
		 */
		Vector stdvball = ball.transformVelocity(triangles[i].tmatrix);
		double stdvballx = stdvball[0];
		double stdvbally = stdvball[1];
		double stdvballz = stdvball[2];
		Vector stdballpos = ball.transformPosition(triangles[i].tmatrix);
		double stdballx = stdballpos[0];
		double stdbally = stdballpos[1];
		double stdballz = stdballpos[2];

		if (stdvbally < 0)
		{
			double testtime = -(stdbally - radius) / (stdvbally); // find time at which ball will hit floor
#if DEBUG
			cerr << "Ball is moving downward" << endl;
			cerr << "testtime = " << testtime << endl;
			cerr << "timeLeft = " << timeLeft << endl;
#endif
			if (testtime >= epsilon && testtime < timeLeft)	// does ball hit floor in next time step?
			{
				// project the ball's expected position onto the triangle to check for collisions
				double testx = stdballx + stdvballx*testtime;
				double testy = stdbally + stdvbally*testtime;
				double testz = stdballz + stdvballz*testtime;

				// This is for checking whether the ball is in the triangle surface.
				double v2x = (triangles[i].sverts[1])[0];
				double v2z = (triangles[i].sverts[1])[2];
				double v3x = (triangles[i].sverts[2])[0];

				double line1 = (v2z/v2x)*testx;
				double line2 = (v2z/(v2x-v3x))*testx - (v2z*v3x)/(v2x-v3x);


				if (v2x == 0)
				{
#if DEBUG
					cerr << "Infinite near slope" << endl;
#endif
					if ((testz > 0) && (testz < line2) && (testx > 0))
					{
#if DEBUG
					cerr << "Ball is within area of triangle" << endl;
#endif
						collidedThisTime = true;
						triangleCollisionTime = testtime;
						normalToAdd = triangles[i].normal;
					}
				}
				else if (v2x-v3x == 0)
				{
#if DEBUG
					cerr << "Infinite far slope" << endl;
#endif
					if ((testz > 0) && (testz < line1) && (testx < v2x))
					{
#if DEBUG
					cerr << "Ball is within area of triangle" << endl;
#endif
						collidedThisTime = true;
						triangleCollisionTime = testtime;
						normalToAdd = triangles[i].normal;
					}
				}
				else if ((testz > 0) && (testz < line1) && (testz < line2))	// ball in triangle?
				{
#if DEBUG
					cerr << "No infinite slopes" << endl;
					cerr << "Ball is within area of triangle" << endl;
#endif
					collidedThisTime = true;
					triangleCollisionTime = testtime;
					normalToAdd = triangles[i].normal;
				}
			}
		}

		if (!collidedThisTime)
		{
			/*
			 * Detect vertices.
			 */
			if (v1test > 0 && v1test < radius)	// ball hit vertex 1?
			{
#if COLLISIONDEBUG
				cerr << "Hit vertex 1: " << v1test << endl;
#endif
				collidedThisTime = true;
				normalToAdd = average(v1 - v3, v1 - v2);
				triangleCollisionTime = v1test / ballspeed;
			}
			else if (v2test > 0 && v2test < radius)	// ball hit vertex 2?
			{
#if COLLISIONDEBUG
				cerr << "Hit vertex 2" << v2test << endl;
#endif
				collidedThisTime = true;
				normalToAdd = average(v2 - v1, v2 - v3);
				triangleCollisionTime = v2test / ballspeed;
			}
			else if (v3test > 0 && v3test < radius)	// ball hit vertex 3?
			{
#if COLLISIONDEBUG
				cerr << "Hit vertex 3" << v3test << endl;
#endif
				collidedThisTime = true;
				normalToAdd = average(v3 - v1, v3 - v2);
				triangleCollisionTime = v3test / ballspeed;
			}

			/*
			 * Detect edges.
			 */
			else if (e1to2test > 0 && e1to2test < radius)	// ball hit edge from vertex 1 to 2?
			{
#if COLLISIONDEBUG
				cerr << "Hit edge 1 to 2" << endl;
#endif
				collidedThisTime = true;
				normalToAdd = (v2 - v1).cross(triangles[i].normal);
				triangleCollisionTime = e1to2test / ballspeed;
			}
			else if (e2to3test > 0 && e2to3test < radius)	// ball hit edge from vertex 2 to 3?
			{
#if COLLISIONDEBUG
				cerr << "Hit edge 2 to 3" << endl;
#endif
				collidedThisTime = true;
				normalToAdd = (v3 - v2).cross(triangles[i].normal);
				triangleCollisionTime = e2to3test / ballspeed;
			}
			else if (e3to1test > 0 && e3to1test < radius)	// ball hit edge from vertex 3 to 1?
			{
#if COLLISIONDEBUG
				cerr << "Hit edge 3 to 1" << endl;
#endif
				collidedThisTime = true;
				normalToAdd = (v3 - v1).cross(triangles[i].normal);
				triangleCollisionTime = e3to1test / ballspeed;
			}
		} // End of checking for particular triangle.

		// Process the collision information from this triangle.
		if (collided && collidedThisTime)
		{
			// New closest triangle to collide with; overwrite
			// old collision data.
			if (triangleCollisionTime < timeElapsed)
			{
#if COLLISIONDEBUG
				cerr << "Adding normal (" << triangles[i].normal[0] << ", " << triangles[i].normal[1] << ", " << triangles[i].normal[2] << ")" << endl;
#endif
				normal = normalToAdd;
				timeElapsed = triangleCollisionTime;
			}
			// Simultaneous collision with multiple triangles;
			// average collision data.
			else if (fabs(triangleCollisionTime - timeElapsed) < EPSILON)
			{
#if COLLISIONDEBUG
				cerr << "Simultaneous collision!" << endl;
				cerr << "Adding normal (" << triangles[i].normal[0] << ", " << triangles[i].normal[1] << ", " << triangles[i].normal[2] << ")" << endl;
#endif
				normal = average(normal, normalToAdd);
			}
		}
		else if (collidedThisTime)
		{
				timeElapsed = triangleCollisionTime;
				normal = normalToAdd;
				// Set collided equal to true, right?
				collided = true;
#if COLLISIONDEBUG
				cerr << "Adding normal (" << triangles[i].normal[0] << ", " << triangles[i].normal[1] << ", " << triangles[i].normal[2] << ")" << endl;
				cerr << "timeElapsed = " << timeElapsed << " and timeLeft = " << timeLeft << endl;
#endif

		}
		collidedThisTime = false;
		// End of checking triangles for collisions.
	}

	// Ball bounces; change its velocity and move it.
	if (collided)
	{
		if (timeLeft > timeElapsed) 
		{
			cerr << "Bouncing the ball and moving it..." << endl;
			ball.bounce(normal);
			ball.move(timeElapsed);
			display();
			timeLeft -= timeElapsed;
#if DEBUG
	cout << "NEW VELOCITY: (" << ball.vel[0] << ", " << ball.vel[1] << ", " << ball.vel[2] << ")" << endl; 
#endif
		}
	}
	else
	{
		ball.move(timeLeft);
		display();
		timeLeft = 0;
	}
}

/*
 * Helpful functions.
 */

/************************************************************/
/*															*/
/*	this routine finds the closest point q on the line		*/
/*	segment defined by the points "start" and "end"			*/
/*	to the point "v"										*/
/*															*/
/*	it returns alpha where q=start + alpha * (end-start)	*/
/*															*/
/************************************************************/
				
double linePointMinimumDistance(const Vector& start, const Vector& end, const Vector& v)
{

	// construct a vector along the line
	Vector v1=end-start;
	double len = v1.length();
	// check if the line is actually a point
	if (len == 0)
		// if so the point start=end is desired point and alpha=0
		return 0; 

	// construct a vector from the line to the point
	Vector v2=v-start;
	// q=start + alpha * v1 is the closest point on the line to the point v
	// where alph is defined below
	double alpha = v1.dot(v2)/(len*len);

	// if q is not on the line segment then an endpoint of the line
	// segment is the desired point
	if (alpha<0)
		alpha=0;
	if (alpha>1)
		alpha=1;
	
	return alpha;
}

//******************************************************************//
//																	//
//	This routine finds to closest points p1 & p2 on two	line		//
//	segments, l1 (start1 to end1) and l2 (start2 to end2)			//
//  It computes alpha and beta in [0,1] such that					//
//		p1 = start1 + alpha * (end1-start1)							//
//		p2 = start2 + beta * (end2-start2)							//
//	If the lines are parallel -- which should never result in a		//
//	collision, it returns alpha=beta=-1								//
//																	//
//******************************************************************//	

void lineLineMinimumDistance(const Vector& start1, const Vector& end1, 
							 const Vector& start2, const Vector& end2, 
							 double& alpha, double& beta)
{



	// find vector along first line
	Vector v1=end1-start1;
	double v1dotv1=v1.dot(v1);
	// check if the line is actually a point
	if (v1dotv1==0) {	
		// first line is really a point
		alpha = 0;
		beta = linePointMinimumDistance(start2, end2, start1);
		return;
	}

	// find vector along second line
	Vector v2=end2-start2;
	double v2dotv2=v2.dot(v2);
	// check if the line is actually a point
	if (v2dotv2==0) {
		// second line is really a point
		alpha = linePointMinimumDistance(start1, end1, start2);
		beta=0;
		return;
	}

	// check if lines are parallel
	double v1dotv2=v2.dot(v1);  // we define both for convenience
	double v2dotv1=v1dotv2;

	if (v2dotv2*v1dotv1 != v2dotv1*v1dotv2) {  // do not parallel case first
		// Find closest point
		Vector s=start2-start1;
		double sdotv1=s.dot(v1);
		double sdotv2=s.dot(v2);

		beta = (sdotv2- sdotv1*v1dotv2/v1dotv1)/(v1dotv2*v2dotv1/v1dotv1 - v2dotv2);
		alpha = (sdotv1 + beta*v2dotv1)/(v1dotv1);

		// if alpha and beta are both on their line segments
		// we are done
		// if not, then at least one of the points we are
		// looking for is an endpoint.  we could test each
		// endpoint to find its closest point on the other
		// line.  this would take four calls to linePointMinimumDistance.
		// if we examine the possible cases, however, we
		// need only compute one call to linePointMinimumDistance.
		// we take that approach.

		// alpha and beta are each in one of three states:
		// 0<= alpha <=1, alpha<0, or alpha>1  
		// 0<= beta <=1,  beta <0, or beta>1
		// thus there are nine states to consider
		// testval represents the states
		int testval = 3*(alpha<0) + 6*(alpha>1) + 1*(beta<0) + 2*(beta>1);

		switch (testval) {
		case 0: {	// alpha and beta are in [0,1]
			return;
				}

		case 1: {	// alpha in [0,1], beta<0
				alpha = linePointMinimumDistance(start1,end1,start2);
				beta=0;
				return;
				}

		case 2: {	// alpha in [0,1], beta>1
				alpha = linePointMinimumDistance(start1,end1,end2);
				beta=1;
				return;
				}

		case 3: {	// alpha < 0, beta in [0,1]
				alpha=0;
				beta=linePointMinimumDistance(start2,end2,start1);
				return;
				}

		case 6: {	// alpha > 1, beta in [0,1]
				alpha=1;
				beta=linePointMinimumDistance(start2,end2,end1);
				return;
				}

		case 5: {  // alpha <0, beta >1
				alpha=0;
				beta=1;
				return;
				}

		case 7: {  // alpha >1, beta <0
				alpha=1;
				beta=0;
				return;
				}

		case 4: {  //alpha < 0, beta < 0
					if ((v1*alpha).length() > (v2*beta).length()) {
						alpha=0;
						beta=linePointMinimumDistance(start2,end2,start1);
					}
					else {
						beta=0;
						alpha = linePointMinimumDistance(start1,end1,start2);
					}
					return;
				}

		case 8: {  // alpha > 1, beta > 1
					if ((start1+v1*alpha-end1).length() > (start2+v2*beta).length()) {
						alpha=1;
						beta=linePointMinimumDistance(start2,end2,end1);
					}
					else {
						beta = 1;
						alpha =	linePointMinimumDistance(start1,end1,end2);
					}

					return;
				}

		}

	}
	else { 

		// the lines are parallel
		// this should never result in a collision
		alpha = -1;
		beta=-1;
		return;
	}
}